/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/restore-ip-addresses
   @Language: C++
   @Datetime: 16-02-09 08:25
   */

class Solution {
	bool isvalid(const string &s){
		// num can not start with zero, except zero num
		if(s.length()<1 || (s[0]=='0' && s!="0")) return false;
		return stoi(s) <256;
	}
	void getip(const string &s,int pos,int dots
			,vector<string> &ips,string &ip){
		if (dots==4){
			if (pos==s.length()){
				ips.push_back(ip);
				ips.back().pop_back();	// trim last dot
			}
			return;
		}
		for (int i=1; i<4 && pos+i<=s.length(); ++i){
			const string str = s.substr(pos,i);
			if(isvalid(str)){
				ip.append(str+".");
				getip(s,pos+i,dots+1,ips,ip);
				ip.erase(ip.length()-i-1);
			}
		}
	}

public:
	/**
	 * @param s the IP string
	 * @return All possible valid IP addresses
	 */
	vector<string> restoreIpAddresses(string& s) {
		// Write your code here
		vector<string> ips;
		string ip;
		getip(s,0,0,ips,ip);
		return ips;
	}
};
